package com.shankar.narayan.ms.screen;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * Utility class to do all forms of reversing. 1. Reversing a string. 2.
 * Reversing the words in a sentence. 3. Reversing a sentence.
 */
public class ReverseString {

	public ReverseString() {
	}

	public String reverseStringNonRecursive(StringBuffer buffer) {
		// non recursive way to reverse a string.
		// following the divide by 2 and 2 pointer way.
		// One pass across the string and in place. O(n) and constant memory of
		// 1 char.

		char temp;
		int length = buffer.length();
		for (int i = 0; i < length / 2; i++) {
			temp = buffer.charAt(i);
			buffer.setCharAt(i, buffer.charAt(length - 1 - i));
			buffer.setCharAt(length - 1 - i, temp);
		}

		return buffer.toString();
	}

	// recursive way to print the string in reverse.
	public String reverseStringRecursive(String str) {
		if (str.length() == 1) {
			return str;
		}
		return str.charAt(str.length() - 1)
				+ reverseStringRecursive(str.subSequence(0, str.length() - 1)
						.toString());
	}

	public String reverseWordsInSentence(String str) {
		// reverse each word individually in the sentence.
		// 1. Reverse whole sentence and pass each word again to double reverse
		// to get the original words.
		// 2. Take each word and return string in the reverse order

		String sentence = reverseStringRecursive(str);
		StringTokenizer token = new StringTokenizer(sentence, " ");

		String result = new String();
		while (token.hasMoreTokens()) {
			result += reverseStringRecursive(token.nextToken()) + " ";
		}
		// account for the extra space appended after the last word
		return result.subSequence(0, result.length() - 1).toString();
	}

	public void permutate(char[] str, int index) {
		// works by fixing one element and rotating the others.
		// O(n*n!) as you need to cycle through all elements for each of the n!
		// attempts.

		int i = 0;
		if (index == str.length) { // We have a permutation so print it
			System.out.print(str);
			System.out.print("\n");
			return;
		}
		for (i = index; i < str.length; i++) {
			// swap
			char temp = str[index];
			str[index] = str[i];
			str[i] = temp;

			permutate(str, index + 1);
			// swap
			temp = str[index];
			str[index] = str[i];
			str[i] = temp;
		}
	}

	public static void main(String[] args) throws IOException {
		System.out.println("Enter the queue length");
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		String str = reader.readLine().toString();
		ReverseString rev = new ReverseString();
		System.out.println("\n1. Non recursive:"
				+ rev.reverseStringNonRecursive(new StringBuffer(str)));
		System.out.println("\n2. Recursive:" + rev.reverseStringRecursive(str));
		System.out.println("\n3. Words in a sentence : "
				+ rev.reverseWordsInSentence(str));
		System.out.println("\n4. Permutations : \n");
		rev.permutate(str.toCharArray(), 0);
	}

}
